Bienvenido a la Clase 2. Tras establecer los objetivos generales de este curso, ahora nos adentramos en las estructuras fundamentales de datosque constituyen los bloques básicos del diseño de algoritmos: arreglos y listas enlazadas.
Los arreglos y las listas enlazadas son las formas más básicas y críticas de organizar datos en memoria, representando el conflicto central entre contiguos y dispersos de gestión de almacenamiento.
Definición:Una estructura de datos es un formato especializado para organizar y almacenar datos con el fin de facilitar el acceso eficiente y la modificación.
- Los arreglos almacenan elementos en contiguosubicaciones de memoria, lo que permite el cálculo directo de las direcciones de los elementos.
- Las listas enlazadas almacenan elementos en dispersosubicaciones de memoria, conectadas únicamente mediante punteros explícitos.
- El acceso a un arreglo es indexación directa ($O(1)$), mientras que el acceso a una lista enlazada requiere recorrido ($O(n)$).
- La inserción o eliminación en un arreglo requiere desplazar elementos, lo que da como resultado $O(n)$ complejidad.
- La inserción o eliminación en una lista enlazada solo requiere reconexión de punteros, logrando $O(1)$ si se conoce la posición $i$.
- Las listas enlazadas tienen un mayor sobrecarga de espacioporque cada nodo debe almacenar datos junto con un puntero `next`.
Comparación de complejidad
| Característica | Arreglo | Lista Enlazada Simple |
|---|---|---|
| Asignación de memoria | Contigua (tamaño fijo de bloque $n$) | Dispersa (punteros dinámicos) |
| Tiempo de acceso | $O(1)$ | $O(n)$ |
| Inserción/Eliminación | $O(n)$ | $O(1)$ (si se conoce la posición $i$) |
| sobrecarga de espacio | Mínima (solo datos) | Alta (datos + next puntero) |